import { TreeNode } from '../base/tree-node';

/**
 * 二叉搜索树的最近公共祖先
 * LeetCode 235
 *
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
 *
 * @param root 二叉搜索树的根节点
 * @param p 第一个节点
 * @param q 第二个节点
 * @returns 最近公共祖先节点
 */
export default function lowestCommonAncestorBST(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  // 基本情况：如果根节点为空，返回null
  if (!root) return null;

  // 利用二叉搜索树的性质进行搜索
  // 如果p和q的值都小于根节点的值，那么它们的最近公共祖先一定在左子树
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestorBST(root.left, p, q);
  }

  // 如果p和q的值都大于根节点的值，那么它们的最近公共祖先一定在右子树
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestorBST(root.right, p, q);
  }

  // 如果一个在左子树，一个在右子树，或者其中一个是根节点，那么根节点就是最近公共祖先
  return root;
}

/**
 * 二叉搜索树的最近公共祖先（迭代版本）
 *
 * @param root 二叉搜索树的根节点
 * @param p 第一个节点
 * @param q 第二个节点
 * @returns 最近公共祖先节点
 */
export function lowestCommonAncestorBSTIterative(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  let current = root;

  while (current) {
    // 如果p和q的值都小于当前节点的值，向左子树移动
    if (p.val < current.val && q.val < current.val) {
      current = current.left;
    }
    // 如果p和q的值都大于当前节点的值，向右子树移动
    else if (p.val > current.val && q.val > current.val) {
      current = current.right;
    }
    // 否则，当前节点就是最近公共祖先
    else {
      return current;
    }
  }

  return null;
}
